자료구조: 연결리스트&스택(Stack)

1. 스택

①스택 선언	②push(), 삽입	③pop(), 삭제
Algorithm size():     return t +1 //인덱스가 0부터 시작 Algorithm isEmpty():     return (t < 0) Algorithm top():     if isEmpty() then       throw a StackEmptyException     return S[t]	Algorithm push(o):     if size() = N then       throw a StackFullException     t ← t + 1     S[t] ← o	Algorithm pop():     if isEmpty() then       throw a StackEmptyException     e ← S[t]     S[t] ← null     t ← t-1     return e

1) 구현

#include <iostream>
#include <conio.h>
 
using namespace std;
 
//#define MAX = 12;
const int MAX = 12;//가급적 const사용
 
//스택
int g_stack[MAX];
int top = -1;
 
void push(int val);
void pop();
void print_stack();
 
void main()
{
    print_stack();
    push(2015);
    push(12);
    push(23);
    push(11);
    print_stack();
    pop();
    pop();
    pop();
    pop();
    pop();
    print_stack();
 
    cout << "PRESS KEY" << endl;
    _getch();
}
 
void push(int val)
{
    if (top + 1 < MAX)
    {
        top++;
        g_stack[top] = val;
    }
    else
    {
        return;
    }
    cout << "idx=" << top << ", top = " << g_stack[top] << endl;
}
 
void pop()
{
    int tmp = g_stack[top];
 
    if (top >= 0)
    {
        g_stack[top] = 0;
        top--;
    }    
 
    cout << "pop: " << tmp << ", new top = " << g_stack[top] << endl;
}
 
void print_stack()
{
    if (top != -1)
    {
        for (int idx = top; idx >= 0; idx--)
        {//스택은 탑->다운이 기본이니깐
            cout << g_stack[idx] << endl;
        }
    }
    else
    {
        cout << "STACK EMPTY\n" << endl;
    }
}

2) 구현, 포인터 및 구조체 사용한 방식

#include <iostream>
#include <conio.h>
using namespace std;
 
//#define MAX= 256;
const int MAX= 256;//가급적 const사용
int pop (struct stack *s_arr);
int push (struct stack *s_arr, int x);
void CreateStack(StackSturct **Stack, int Capacity);
void DestroyStack(StackSturct **Stack);
 
struct stack_arr
{
   int item[MAX_SIZE];
   int top;
}
 
typedef struct Node
{
     int Data; //굳이 int로 한정되진 않음.
}Node;
 
typedef struct Stack
{
     int Capacity;
     int Top;
     Node *Nodes;
}StackSturct;
 
void main()
{
    cout << "PRESS KEY" << endl;
    _getch();}
}
 
int pop (struct stack *s_arr)
{
   int  pop_val;
 
   if(s_arr->top == -1)
   {
      printf("스텍 언더플로우");
      exit();
   }
   pop =  s_arr->item[s_arr->top--];
 
   return (pop_val);
}
 
int push (struct stack *s_arr, int x)
{
   if(s_arr->top ==  MAX_SIZE)
   {
      printf("스텍 오버플로우");
      exit();
   }
   s_arr->item[++s_arr->top];
}
 
void CreateStack(StackSturct **Stack, int Capacity)
{
     (*Stack) = new StackSturct;//(StackSturct *)malloc(sizeof(StackSturct));
 
     //노드*단위용량만큼 메모리.
     (*Stack)->Nodes = new Node;//(Node *)malloc(sizeof(Node) *Capacity);
 
     /* 용량, TOP 초기화 */
     (*Stack)->Capacity = Capacity;
     (*Stack)->Top = 0;
}
 
void DestroyStack(StackSturct **Stack)
{
      //free(Stack->Nodes); //노드해제
    //free(Stack);        //스택해제
    Stack->Nodes = NULL;
    Stack = NULL:
}

2. 연결리스트

#include <iostream>
#include <conio.h>
 
using namespace std;
 
//일반 연결 리스트
typedef struct list_linked
{
    int key;
    struct list_linked *next;//다음 노드 위치 저장.//이 경우 재귀적인 정의.
}node_link;
node_link *head, *tail;//*next값을 변경하기 좋은 포인터 태그.
 
node_link *node_insert1(int num, node_link *new_tail);
int node_del(node_link *target);
node_link *node_find(int key);
 
void main()
{
    head = new node_link;
    tail = new node_link;
 
    head->next = tail;
    tail->next = tail;//꼬리에서 흐름이 끝나게 하는 부분.
 
 
    cout << "PRESS KEY" << endl;
    _getch();
}
 
//================================================================================
//    노드제어 관련.
//================================================================================
node_link *node_insert1(int num, node_link *exist_node)
{//특정 노드 뒤에 삽입
    node_link *node_new = NULL;
    node_new = new node_link;
    node_new->key = num;
    node_new->next = exist_node->next;//exist_node와 exist_node->next 사이에 삽입되므로
    exist_node->next = node_new;
 
    return node_new;
}
 
node_link *node_insert2(int preKey, int nextKey)
{//키값을 기준으로 두 노드사이에 삽입
    //node_find와 node_insert1를 응용
}
 
int node_del(node_link *target)
{//target의 다음 노드를 삭제
    node_link *tmp = NULL;
    int result = 0;
 
    if (target->next == tail)
        result = 0;
    else
    {
        tmp = target->next;
        target->next = target->next->next;
        tmp = NULL;
        result = 1;
    }
 
    return result;
}
 
node_link *node_find(int key)
{
    node_link *tmp = NULL;
    tmp = head->next;
 
    while (tmp->key != key && tmp != tail)
    {
        cout << "tmp=" << tmp << ", tmp->key=" << tmp->key << endl;
        tmp = tmp->next;
    }
 
    return tmp;
}

3. 연결리스트 스택(Linked List Stack)

-> 메모리 동적할당이라 스택을 구현하는데 아주 유용.

-> 스택의 크기가 고정되지 않음. 스택내 데이터의 개수만큼만 메모리를 사용.

①스택 선언	②push(), 삽입	③pop(), 삭제
typedef struct tagNode {    //int Data; //굳이 int로 한정되진 않음.    char *Data; //linkde_value의 주소값.    struct tagNode *NextNode; }NodeStruct; typedef struct tagStack {    int Capacity;    int Top;    NodeStruct *Nodes; }StackSturct; typedef struct tagLinkedListStack {    Node *List;    Node *Top; }LLS_Struct;	void LSS_Push(LLS_Struct **Stack,                       Node *NewNode) {    if (Stack->List == NULL)    {       Stack->List = NewNode;    } //공백스택이면, 새노드가 리스트에 곧장 들어감.    else    {       Node *OldTop = Stack->List;;       while (OldTop->NextNode != NULL)       {          OldTop = OldTop->NextNode;       }       OldTop->NextNode = NewNode;    }    Stack->Top = NewNode; }	void LLS_Pop(LLS_Struct **Stack) {    Node *TopNode = Stack->Top;    if (Stack->List == Stack->Top)    {       Stack->List = NULL;       Stack->Top = NULL;    }    else    {       Node *CurrentTop = Stack->List;       while (CurrentTop != NULL                 &&                 CurrentTop->NextNode != Stack->Top)       {          CurrentTop = CurrentTop->NextNode;       }       Stack->Top = CurrentTop;       CurrentTop->NextNode = NULL;    }    return TopNode; }

typedef struct tagNode
{
   //int Data; //굳이 int로 한정되진 않음.
   char *Data; //포인터형(char *)은 단순히 값의 복사가 아니라, linkde_value의 주소값.
   struct tagNode *NextNode;
}NodeStruct;
typedef struct tagStack
{
   int Capacity;
   int Top;
   NodeStruct *Nodes;
}StackSturct;
typedef struct tagLinkedListStack
{
   Node *List;
   Node *Top;
}LLS_Struct;
 
void LSS_CreateStack(LLS_Struct **Stack) //스택생성
{
   (*Stack) = (LLS_Struct*)malloc(sizeof(LLS_Struct)); //자유저장소 할당.
   (*Stack)->List = NULL;
   (*Stack)->Top = NULL;
}
 
void LSS_DestroyStack(LLS_Struct **Stack) //노드소멸
{
   while( !LLS_isEmpty(Stack) )
   {
      Node *Popped = LLS_Pop(Stack);
      LLs_DestroyNode(Popped);
   }
   free(Stack);
}
 
void LSS_CreateNode(char *NewData) //노드생성
{
   Node *NewNode = (Node*)malloc(sizeof(Node));
   NewNode->Data = (char*)malloc(strlen(NewData) + 1);//입력받은 문자열 크기로 자유 저장소
   strcpy(NewNode->Data, NewData);//문자열 복사
   NewDode->NextNode = NULL:
 
   return NewNode;//노드주소 반환
}
 
void LSS_DestroyNode(Node * _Node) //노드소멸
{
   free(_Node->Data);
   free(_Node);
}
 
void LSS_Push(LLS_Struct **Stack, Node *NewNode)//스택삽입
{
   if (Stack->List == NULL)
   {
      Stack->List = NewNode;
   } //텅빈 스택이면, 새노드가 리스트에 곧장 들어감.
   else
   {
      Node *OldTop = Stack->List;;
      while (OldTop->NextNode != NULL)
      {
         OldTop = OldTop->NextNode;
      }
      OldTop->NextNode = NewNode;
   }
   Stack->Top = NewNode;
}
 
void LLS_Pop(LLS_Struct **Stack)
{
   Node *TopNode = Stack->Top;
 
   if (Stack->List == Stack->Top)
   {
      Stack->List = NULL;
      Stack->Top = NULL;
   }
   else
   {
      Node *CurrentTop = Stack->List;
      while (CurrentTop != NULL && CurrentTop->NextNode != Stack->Top)
      {
         CurrentTop = CurrentTop->NextNode;
      }
      Stack->Top = CurrentTop;
      CurrentTop->NextNode = NULL;
   }
   return TopNode;
}

기타. 변경이력

일자	변경이력
2012-01-09	초안.
2015-12-23	가독성 개선 및 기본형 예시코드 2종 추가