데이터 구조 - 선형 표 - 스 택

스 택: 후진 선 출 (LIFO) last in first out 스 택 은 특수 한 선형 표 로 선형 표 의 한 끝 에서 만 조작 할 수 있 습 니 다.창고 꼭대기 상단 창고 바닥
실현 방식: 순서 구조 실현, 선형 구조 실현
 
체인 메모리 구현
LinkStack.h

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_

typedef void LinkStack;

LinkStack* LinkStack_Create();

void LinkStack_Destroy(LinkStack* stack);

void LinkStack_Clear(LinkStack* stack);

int LinkStack_Push(LinkStack* stack, void* item);

void* LinkStack_Pop(LinkStack* stack);

void* LinkStack_Top(LinkStack* stack);

int LinkStack_Size(LinkStack* stack);

#endif

LinkStack.c

#include <malloc.h>
#include "LinkStack.h"
#include "LinkList.h"

typedef struct _tag_LinkStackNode
{
    LinkListNode header;
    void* item;
} TLinkStackNode;

LinkStack* LinkStack_Create()
{
    return LinkList_Create();
}

void LinkStack_Destroy(LinkStack* stack)
{
    LinkStack_Clear(stack);
    LinkList_Destroy(stack);
}

void LinkStack_Clear(LinkStack* stack)
{
    while( LinkStack_Size(stack) > 0 )
    {
        LinkStack_Pop(stack);
    }
}

int LinkStack_Push(LinkStack* stack, void* item)
{
    TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode));
    int ret = (node != NULL) && (item != NULL);
    
    if( ret )
    {
        node->item = item;
        
        ret  = LinkList_Insert(stack, (LinkListNode*)node, 0);
    }
    
    if( !ret )
    {
        free(node);
    }
    
    return ret;
}

void* LinkStack_Pop(LinkStack* stack)
{
    TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0);
    void* ret = NULL;
    
    if( node != NULL )
    {
        ret = node->item;
        
        free(node);
    }
    
    return ret;
}

void* LinkStack_Top(LinkStack* stack)
{
    TLinkStackNode* node = (TLinkStackNode*)LinkList_Get(stack, 0);
    void* ret = NULL;
    
    if( node != NULL )
    {
        ret = node->item;
    }
    
    return ret;
}

int LinkStack_Size(LinkStack* stack)
{
    return LinkList_Length(stack);
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) 
{
    LinkStack* stack = LinkStack_Create();
    int a[10];
    int i = 0;
    
    for(i=0; i<10; i++)
    {
        a[i] = i;
        
        LinkStack_Push(stack, a + i);
    }
    
    printf("Top: %d
", *(int*)LinkStack_Top(stack));
    printf("Length: %d
", LinkStack_Size(stack));
    
    while( LinkStack_Size(stack) > 0 )
    {
        printf("Pop: %d
", *(int*)LinkStack_Pop(stack));
    }
    
    LinkStack_Destroy(stack);
    
    return 0;
}

 
순차 저장 실현:
SeqStack.h

#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_

typedef void SeqStack;

SeqStack* SeqStack_Create(int capacity);

void SeqStack_Destroy(SeqStack* stack);

void SeqStack_Clear(SeqStack* stack);

int SeqStack_Push(SeqStack* stack, void* item);

void* SeqStack_Pop(SeqStack* stack);

void* SeqStack_Top(SeqStack* stack);

int SeqStack_Size(SeqStack* stack);

int SeqStack_Capacity(SeqStack* stack);

#endif

SeqStack.c

#include "SeqStack.h"
#include "SeqList.h"

SeqStack* SeqStack_Create(int capacity)
{
    return SeqList_Create(capacity);
}

void SeqStack_Destroy(SeqStack* stack)
{
    SeqList_Destroy(stack);
}

void SeqStack_Clear(SeqStack* stack)
{
    SeqList_Clear(stack);
}

int SeqStack_Push(SeqStack* stack, void* item)
{
    return SeqList_Insert(stack, item, SeqList_Length(stack));
}

void* SeqStack_Pop(SeqStack* stack)
{
    return SeqList_Delete(stack, SeqList_Length(stack) - 1);
}

void* SeqStack_Top(SeqStack* stack)
{
    return SeqList_Get(stack, SeqList_Length(stack) - 1);
}

int SeqStack_Size(SeqStack* stack)
{
    return SeqList_Length(stack);
}

int SeqStack_Capacity(SeqStack* stack)
{
    return SeqList_Capacity(stack);
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "SeqStack.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) 
{
    SeqStack* stack = SeqStack_Create(20);
    int a[10];
    int i = 0;
    
    for(i=0; i<10; i++)
    {
        a[i] = i;
        
        SeqStack_Push(stack, a + i);
    }
    
    printf("Top: %d
", *(int*)SeqStack_Top(stack));
    printf("Capacity: %d
", SeqStack_Capacity(stack));
    printf("Length: %d
", SeqStack_Size(stack));
    
    while( SeqStack_Size(stack) > 0 )
    {
        printf("Pop: %d
", *(int*)SeqStack_Pop(stack));
    }
    
    SeqStack_Destroy(stack);
    
    return 0;
}

 
창고 의 특별 실현
q1 은 전문 적 으로 창고 에 드 나 드 는 것 이 고 q2 는 중간 역 일 뿐 입 니 다.요 소 는 한 창고 에 집중 적 으로 저 장 됩 니 다 (q1 또는 q2, 상황 에 따라 변 동 됩 니 다)
두 개의 지침 을 정의 합 니 다: pushtmp: 스 택 에 전문 적 으로 들 어 가 는 대기 열 q1 을 가리 킵 니 다.tmp: 중간 역 으로 임시 스 택 q2
스 택 에 들 어가 기: pushtmp 가 가리 키 는 대기 열 에 직접 들 어가 면 스 택 을 나 갈 수 있 습 니 다. pushtmp 의 마지막 요 소 를 제외 하고 모두 대기 열 tmp 로 옮 긴 다음 방금 남 은 q1 의 요 소 를 대기 열 에서 나 옵 니 다.
참고:http://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html　　
 
창고 의 용도:
서로 인접 하지 않 고 서로 일치 하 는 사물 은 가 까 운 곳 에서 일치 하 는 장소 에 매우 적합 하 다.
1. 검 측 코드 에서 괄호 가 일치 하 는 지 여부
원리:
 
1. 왼쪽 에서 오른쪽으로 스 캔
2. 일반 문자 가 무시 되 고 기호 가 창고 에 들 어 가 는 것 을 만 났 습 니 다.
3. 기호 가 창고 에서 나 오 는 경우
4 、 매 칭 진행
매 칭 성공 후 다음 계속
일치 실패, 오류 보고 중지
5. 끝
성공: 모든 문자 스 캔 이 완료 되 었 고 스 택 이 비어 있 습 니 다.
실패: 일치 실패 또는 스 캔 완료 스 택 이 비어 있 지 않 습 니 다.
 
 
괄호 일치 여부 확인
main.c

#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int isLeft(char c)
{
    int ret = 0;
    
    switch(c)
    {
        case '<':
        case '(':
        case '[':
        case '{':
        case '\'':
        case '\"':
            ret = 1;
            break;
        default:
            ret = 0;
            break;
    }
    
    return ret;
}

int isRight(char c)
{
    int ret = 0;
    
    switch(c)
    {
        case '>':
        case ')':
        case ']':
        case '}':
        case '\'':
        case '\"':
            ret = 1;
            break;
        default:
            ret = 0;
            break;
    }
    
    return ret;
}

int match(char left, char right)
{
    int ret = 0;
    
    switch(left)
    {
        case '<':
            ret = (right == '>');
            break;
        case '(':
            ret = (right == ')');
            break;
        case '[':
            ret = (right == ']');
            break;
        case '{':
            ret = (right == '}');
            break;
        case '\'':
            ret = (right == '\'');
            break;
        case '\"':
            ret = (right == '\"');
            break;
        default:
            ret = 0;
            break;
    }
    
    return ret;
}

int scanner(const char* code)
{
    LinkStack* stack = LinkStack_Create();
    int ret = 0;
    int i = 0;
    
    while( code[i] != '\0' )
    {
        if( isLeft(code[i]) )
        {
            LinkStack_Push(stack, (void*)(code + i));
        }
        
        if( isRight(code[i]) )
        {
            char* c = (char*)LinkStack_Pop(stack);
            
            if( (c == NULL) || !match(*c, code[i]) )
            {
                printf("%c does not match!
", code[i]);
                ret = 0;
                break;
            }
        }
        
        i++;
    }
    
    if( (LinkStack_Size(stack) == 0) && (code[i] == '\0') )
    {
        printf("Succeed!
");
        ret = 1;
    }
    else
    {
        printf("Invalid code!
");
        ret = 0;
    }
    
    LinkStack_Destroy(stack);
    
    return ret;
}

int main(int argc, char *argv[])
{
    const char* code = "#include <stdio.h> int main() { int a[5][5]; int (*p)[4]; p = a[0]; printf(\"%d\
\", &p[3][3] - &a[3][3]); return 0; }";
    
    scanner(code);
    
    return 0;
}

 
2. 컴퓨터 로 수학 연산 하기
접미사 표현 식 은 우리 의 읽 기 습관 에 부합 되 고 접미사 표현 식 은 컴퓨터 연산 습관 에 부합된다.
접두사 접두사 계산 방식:
접미사 식 의 숫자 와 기 호 를 옮 겨 다 니 기
숫자: 직접 출력
기호:
왼쪽 괄호: 스 택 에 들 어가 기
기호: 스 택 상단 기호 와 우선 순위 비교
스 택 상단 기호 우선 순위 낮 음: 스 택 에 들 어가 기
기타 상황 (높 거나 같 거나 괄호 와 스 택 이 비어 있 는 것 이 가장 낮다 고 생각 함): 스 택 상단 기 호 를 비어 있 거나 현재 기호 보다 우선 순위 가 낮 을 때 까지 팝 업 한 다음 에 스 택 에 들 어 갑 니 다.
오른쪽 괄호: 왼쪽 괄호 와 일치 할 때 까지 스 택 상단 부 호 를 팝 업 합 니 다.
반복 끝: 스 택 에 있 는 모든 기 호 를 팝 업 합 니 다.
　
접미사 접미사:

#include <stdio.h>
#include "LinkStack.h"

int isNumber(char c)
{
    return ('0' <= c) && (c <= '9');
}

int isOperator(char c)
{
    return (c == '+') || (c == '-') || (c == '*') || (c == '/');
}

int isLeft(char c)
{
    return (c == '(');
}

int isRight(char c)
{
    return (c == ')');
}

int priority(char c)
{
    int ret = 0;
    
    if( (c == '+') || (c == '-') )
    {
        ret = 1;
    }
    
    if( (c == '*') || (c == '/') )
    {
        ret = 2;
    }
    
    return ret;
}

void output(char c)
{
    if( c != '\0' )
    {
        printf("%c", c);
    }
}

void transform(const char* exp)
{
    LinkStack* stack = LinkStack_Create();
    int i = 0;
    
    while( exp[i] != '\0' )
    {
        if( isNumber(exp[i]) )
        {
            output(exp[i]);
        }
        else if( isOperator(exp[i]) )
        {
            //        ，               
            while( priority(exp[i]) <= priority((char)(int)LinkStack_Top(stack)) )
            {
                output((char)(int)LinkStack_Pop(stack));
            }
            
            LinkStack_Push(stack, (void*)(int)exp[i]);
        } 
        else if( isLeft(exp[i]) )
        {
            LinkStack_Push(stack, (void*)(int)exp[i]);
        } 
        else if( isRight(exp[i]) )
        {
            char c = '\0';
            
            while( !isLeft((char)(int)LinkStack_Top(stack)) )
            {
                output((char)(int)LinkStack_Pop(stack));
            }
            
            LinkStack_Pop(stack);
        }
        else
        {
            printf("Invalid expression!");
            break;
        }
        
        i++;
    }
    
    while( (LinkStack_Size(stack) > 0) && (exp[i] == '\0') )
    {
        output((char)(int)LinkStack_Pop(stack));
    }
    
    LinkStack_Destroy(stack);
}

int main()
{
    transform("9+(3-1)*5+8/2");
    
    printf("
");
    
    return 0;
}

 
접미사 계산:

#include <stdio.h>
#include "LinkStack.h"

int isNumber(char c)
{
    return ('0' <= c) && (c <= '9');
}

int isOperator(char c)
{
    return (c == '+') || (c == '-') || (c == '*') || (c == '/');
}

int value(char c)
{
    return (c - '0');
}

int express(int left, int right, char op)
{
    int ret = 0;
    
    switch(op)
    {
        case '+':
            ret = left + right;
            break;
        case '-':
            ret = left - right;
            break;
        case '*':
            ret = left * right;
            break;
        case '/':
            ret = left / right;
            break;
        default:
            break;
    }
    
    return ret;
}

int compute(const char* exp)
{
    LinkStack* stack = LinkStack_Create();
    int ret = 0;
    int i = 0;
    
    while( exp[i] != '\0' )
    {
        if( isNumber(exp[i]) )
        {
            LinkStack_Push(stack, (void*)value(exp[i]));
        }
        else if( isOperator(exp[i]) )
        {
            int right = (int)LinkStack_Pop(stack);
            int left = (int)LinkStack_Pop(stack);
            int result = express(left, right, exp[i]);
            
            LinkStack_Push(stack, (void*)result);
        }
        else
        {
            printf("Invalid expression!");
            break;
        }
        
        i++;
    }
    
    if( (LinkStack_Size(stack) == 1) && (exp[i] == '\0') )
    {
        ret = (int)LinkStack_Pop(stack);
    } 
    else 
    {
        printf("Invalid expression!");
    }
    
    LinkStack_Destroy(stack);
    
    return ret;
}

int main()
{
    printf("9 + (3 - 1) * 5 + 8 / 2 = %d
", compute("931-5*+82/+"));
    
    return 0;
}

 
3. 진 변환
4. 미궁 문제
　　http://www.cnblogs.com/liuling/archive/2013/04/29/mazestack.html
5. 역사 기록
 6. 한 노 타