스택 데이터 구조 는 선형 데이터 구조 다음은 LIFO(후입선출) 원리 이므로 마지막으로 삽입된 요소가 가장 먼저 팝아웃됩니다. 이 기사에서는 스택 기반의 모든 문제를 해결하는 데 도움이 되는 스택의 모든 기본 사항, 스택 작업, 구현, 장점, 단점을 다룰 것입니다.
내용의 테이블
- 스택 데이터 구조란 무엇입니까?
- 스택 데이터 구조의 기본 작업
- 스택 데이터 구조에 대한 연산의 복잡성 분석
- 스택 데이터 구조의 장점
- 스택 데이터 구조의 단점
- 스택 데이터 구조의 응용
스택 데이터 구조란 무엇입니까?
스택 는 선형 데이터 구조 기반으로 LIFO(후입선출) 원리 새 요소의 삽입과 기존 요소의 제거는 다음과 같이 표시된 동일한 끝에서 발생합니다. 맨 위 스택의.
스택을 구현하려면 다음을 유지해야 합니다. 스택의 맨 위를 가리키는 포인터 , 이는 삽입될 마지막 요소입니다. 스택의 맨 위에 있는 요소에만 액세스할 수 있습니다.
스택 데이터 구조의 표현:
스택은 LIFO(Last In First Out) 원리를 따르므로 마지막에 푸시된 요소가 먼저 팝됩니다.
고정 크기 스택 : 이름에서 알 수 있듯이 고정 크기 스택은 고정된 크기를 가지며 동적으로 늘어나거나 줄어들 수 없습니다. 스택이 가득 차고 여기에 요소를 추가하려고 하면 오버플로 오류가 발생합니다. 스택이 비어 있고 스택에서 요소를 제거하려고 하면 언더플로 오류가 발생합니다.
스택의 기본 작업 데이터 구조 :
스택을 조작하기 위해 우리에게 제공되는 특정 작업이 있습니다.
무엇이 PC를 빠르게 만드는가?
- 푸시() 스택에 요소를 삽입하려면
- 팝() 스택에서 요소를 제거하려면
- 맨 위() 스택의 최상위 요소를 반환합니다.
- 비었다() 스택이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
- 가득() 스택이 가득 차면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
푸시 작업 알고리즘:
- 요소를 스택에 푸시하기 전에 스택이 있는지 확인합니다. 가득한 .
- 스택이 가득 찬 경우 (상단 == 용량-1) , 그 다음에 스택 오버플로 스택에 요소를 삽입할 수 없습니다.
- 그렇지 않으면 top 값을 1씩 증가시킵니다. (상단 = 상단 + 1) 새 값은 다음 위치에 삽입됩니다. 최상위 위치 .
- 요소는 우리가 도달할 때까지 스택에 푸시될 수 있습니다. 용량 스택의.
팝 작업을 위한 알고리즘:
- 스택에서 요소를 팝하기 전에 스택이 다음과 같은지 확인합니다. 비어 있는 .
- 스택이 비어 있으면(top == -1) 스택 언더플로우 그리고 스택에서 어떤 요소도 제거할 수 없습니다.
- 그렇지 않으면 상단에 값을 저장하고 상단의 값을 1씩 감소시킵니다. (상단 = 상단 – 1) 저장된 최고 값을 반환합니다.
최고 작업을 위한 알고리즘:
- 스택에서 최상위 요소를 반환하기 전에 스택이 비어 있는지 확인합니다.
- 스택이 비어 있으면(top == -1) 간단히 Stack isempty를 인쇄합니다.
- 그렇지 않으면 다음에 저장된 요소를 반환합니다. 지수=상단 .
isEmpty 작업의 알고리즘 :
- 값을 확인하세요. 맨 위 스택에.
- 만약에 (상단 == -1) , 그러면 스택은 비어 있는 그러니 돌아오세요 진실 .
- 그렇지 않으면 스택이 비어 있지 않으므로 반환합니다. 거짓 .
isFull 작업의 알고리즘:
- 값을 확인하세요. 맨 위 스택에.
- 만약에 (상단 == 용량-1), 그러면 스택은 가득한 그러니 돌아오세요 진실 .
- 그렇지 않으면 스택이 가득 차지 않으므로 반환합니다. 거짓 .
스택 구현 데이터 구조 :
스택에서 수행할 수 있는 기본 작업에는 푸시(push), 팝(pop), 픽(peek)이 있습니다. 스택을 구현하는 방법에는 두 가지가 있습니다.
- 배열 사용
- 연결리스트 사용
배열 기반 구현에서 푸시 작업은 최상위 요소의 인덱스를 증가시키고 해당 인덱스에 새 요소를 저장하여 구현됩니다. 팝 연산은 최상위 인덱스에 저장된 값을 반환한 다음 최상위 요소의 인덱스를 감소시키는 방식으로 구현됩니다.
연결된 목록 기반 구현에서 푸시 작업은 새 요소로 새 노드를 만들고 현재 최상위 노드의 다음 포인터를 새 노드로 설정하여 구현됩니다. Pop 연산은 현재 최상위 노드의 다음 포인터를 다음 노드로 설정하고 현재 최상위 노드의 값을 반환하는 방식으로 구현됩니다.
/* 기본 스택을 구현하는 C++ 프로그램 작업 */ #포함하다 #포함하다 사용하여 네임스페이스 성병; #MAX 1000 정의 수업 스택 { 정수 맨 위; 공공의: 정수 ㅏ[최대]; // 스택의 최대 크기 스택() { 맨 위 = -1; } 부울 푸시(정수 엑스); 정수 팝(); 정수 몰래 엿보다(); 부울 비었다(); }; 부울 스택::푸시(정수 엑스) { 만약에 (맨 위 >= (최대 - 1)) { 시합 << ' 스택='' 오버플로'<='' span=''>; 반품 거짓; } 또 다른 { ㅏ[++맨 위] = 엑스; 시합 << 엑스 << ' 스택에 푸시됨N'; 반품 진실; } } 정수 스택::팝() { 만약에 (맨 위 < 0) { 시합 << '스택 언더플로우'; 반품 0; } 또 다른 { 정수 엑스 = ㅏ[맨 위--]; 반품 엑스; } } 정수 스택::피크() { 만약에 (맨 위 < 0) { 시합 << '스택이 비어 있습니다'; 반품 0; } 또 다른 { 정수 엑스 = ㅏ[맨 위]; 반품 엑스; } } 부울 스택::isEmpty() { 반품 (맨 위 < 0); } // 위의 기능을 테스트하기 위한 드라이버 프로그램 정수 기본() { 수업 스택 에스; 에스.푸시(10); 에스.푸시(이십); 에스.푸시(30); 시합 << 에스.팝() << ' 스택에서 팝됨N'; //팝업 후 스택의 최상위 요소를 인쇄합니다. 시합 << '최상위 요소는 다음과 같습니다. ' << 에스.몰래 엿보다() << 끝; //스택의 모든 요소를 인쇄합니다. 시합 <<'스택에 존재하는 요소: '; ~하는 동안(!에스.비었다()) { //스택의 최상위 요소를 인쇄합니다. 시합 << 에스.몰래 엿보다() <<' '; //스택의 최상위 요소 제거 에스.팝(); } 반품 0; } //코드는 Vinay Pandey에 의해 수정되었습니다.씨 // C program for array implementation of stack #include #include #include // A structure to represent a stack struct Stack { int top; unsigned capacity; int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack->용량 = 용량; 스택->탑 = -1; 스택->배열 = (int*)malloc(스택->용량 * sizeof(int)); 스택 반환; } // top이 마지막 인덱스와 같을 때 스택이 가득 찼습니다. int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // top이 -1과 같을 때 스택은 비어 있습니다. int isEmpty(struct Stack* stack) { return stack->top == -1; } // 스택에 항목을 추가하는 함수입니다. top을 1만큼 증가시킵니다. void push(struct Stack* stack, int item) { if (isFull(stack)) return; 스택->배열[++stack->top] = 항목; printf('%d가 스택에 푸시되었습니다
', item); } // 스택에서 항목을 제거하는 함수입니다. 상단을 1만큼 감소시킵니다. int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return 스택->배열[스택->top--]; } // 스택을 제거하지 않고 스택의 맨 위를 반환하는 함수 int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return 스택->배열[stack->top]; } // 위 함수를 테스트하기 위한 드라이버 프로그램 int main() { struct Stack* stack = createStack(100); 푸시(스택, 10); 푸시(스택, 20); 푸시(스택, 30); printf('%d가 스택에서 팝되었습니다
', pop(stack)); 0을 반환합니다. }> 자바 /* Java program to implement basic stack operations */ class Stack { static final int MAX = 1000; int top; int a[] = new int[MAX]; // Maximum size of Stack boolean isEmpty() { return (top < 0); } Stack() { top = -1; } boolean push(int x) { if (top>= (MAX - 1)) { System.out.println('스택 오버플로'); 거짓을 반환; } else { a[++top] = x; System.out.println(x + ' 스택에 푸시됨'); 사실을 반환; } } int pop() { if (위쪽< 0) { System.out.println('Stack Underflow'); return 0; } else { int x = a[top--]; return x; } } int peek() { if (top < 0) { System.out.println('Stack Underflow'); return 0; } else { int x = a[top]; return x; } } void print(){ for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]); } } } // 드라이버 코드 클래스 Main { public static void main(String args[]) { Stack s = new Stack(); s.push(10); s.push(20); s.push(30); System.out.println(s.pop() + ' 스택에서 팝됨'); System.out.println('최상위 요소는 :' + s.peek()); System.out.print('스택에 있는 요소:'); 스프린트(); } } //이 코드는 Vinay Pandey에 의해 수정되었습니다.> 파이썬 # Python program for implementation of stack # import maxsize from sys module # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack')>
씨# // C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack { private int[] ele; private int top; private int max; public Stack(int size) { ele = new int[size]; // Maximum size of Stack top = -1; max = size; } public void push(int item) { if (top == max - 1) { Console.WriteLine('Stack Overflow'); return; } else { ele[++top] = item; } } public int pop() { if (top == -1) { Console.WriteLine('Stack is Empty'); return -1; } else { Console.WriteLine('{0} popped from stack ', ele[top]); return ele[top--]; } } public int peek() { if (top == -1) { Console.WriteLine('Stack is Empty'); return -1; } else { Console.WriteLine('{0} popped from stack ', ele[top]); return ele[top]; } } public void printStack() { if (top == -1) { Console.WriteLine('Stack is Empty'); return; } else { for (int i = 0; i <= top; i++) { Console.WriteLine('{0} pushed into stack', ele[i]); } } } } // Driver program to test above functions class Program { static void Main() { Stack p = new Stack(5); p.push(10); p.push(20); p.push(30); p.printStack(); p.pop(); } } }> 자바스크립트 /* javascript program to implement basic stack operations */ var t = -1; var MAX = 1000; var a = Array(MAX).fill(0); // Maximum size of Stack function isEmpty() { return (t < 0); } function push(x) { if (t>= (MAX - 1)) { console.log('스택 오버플로'); 거짓을 반환; } else { t+=1; a[t] = x; console.log(x + ' 스택에 푸시됨 '); 사실을 반환; } } 함수 팝() { if (t< 0) { console.log('Stack Underflow'); return 0; } else { var x = a[t]; t-=1; return x; } } function peek() { if (t < 0) { console.log('Stack Underflow'); return 0; } else { var x = a[t]; return x; } } function print() { for (i = t; i>-1; i--) { console.log(' ' + a[i]); } } 푸시(10); 푸시(20); 푸시(30); console.log(pop() + ' 스택에서 팝됨'); console.log(' 최상위 요소는 :' + peek()); console.log(' 스택에 있는 요소: '); 인쇄(); // 이 코드는 Rajput-Ji가 제공한 것입니다.>
산출 10 pushed into stack 20 pushed into stack 30 pushed into stack 30 Popped from stack Top element is : 20 Elements present in stack : 20 10>
어레이 구현의 장점:
- 구현하기 쉽습니다.
- 포인터가 포함되지 않으므로 메모리가 저장됩니다.
어레이 구현의 단점:
- 동적이지 않습니다. 즉, 런타임 시 필요에 따라 늘어나거나 줄어들지 않습니다. [그러나 C++의 벡터, Python의 목록, Java의 ArrayList와 같은 동적 크기 배열의 경우 배열 구현에 따라 스택이 늘어나고 줄어들 수도 있습니다].
- 스택의 전체 크기를 미리 정의해야 합니다.
// C program for array implementation of stack #include #include #include // A structure to represent a stack struct Stack { int top; unsigned capacity; int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack->용량 = 용량; 스택->탑 = -1; 스택->배열 = (int*)malloc(스택->용량 * sizeof(int)); 스택 반환; } // top이 마지막 인덱스와 같을 때 스택이 가득 찼습니다. int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // top이 -1과 같을 때 스택은 비어 있습니다. int isEmpty(struct Stack* stack) { return stack->top == -1; } // 스택에 항목을 추가하는 함수입니다. top을 1만큼 증가시킵니다. void push(struct Stack* stack, int item) { if (isFull(stack)) return; 스택->배열[++stack->top] = 항목; printf('%d가 스택에 푸시되었습니다
', item); } // 스택에서 항목을 제거하는 함수입니다. 상단을 1만큼 감소시킵니다. int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return 스택->배열[스택->top--]; } // 스택을 제거하지 않고 스택의 맨 위를 반환하는 함수 int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return 스택->배열[stack->top]; } // 위 함수를 테스트하기 위한 드라이버 프로그램 int main() { struct Stack* stack = createStack(100); 푸시(스택, 10); 푸시(스택, 20); 푸시(스택, 30); printf('%d가 스택에서 팝되었습니다
', pop(stack)); 0을 반환합니다. }> /* Java program to implement basic stack operations */ class Stack { static final int MAX = 1000; int top; int a[] = new int[MAX]; // Maximum size of Stack boolean isEmpty() { return (top < 0); } Stack() { top = -1; } boolean push(int x) { if (top>= (MAX - 1)) { System.out.println('스택 오버플로'); 거짓을 반환; } else { a[++top] = x; System.out.println(x + ' 스택에 푸시됨'); 사실을 반환; } } int pop() { if (위쪽< 0) { System.out.println('Stack Underflow'); return 0; } else { int x = a[top--]; return x; } } int peek() { if (top < 0) { System.out.println('Stack Underflow'); return 0; } else { int x = a[top]; return x; } } void print(){ for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]); } } } // 드라이버 코드 클래스 Main { public static void main(String args[]) { Stack s = new Stack(); s.push(10); s.push(20); s.push(30); System.out.println(s.pop() + ' 스택에서 팝됨'); System.out.println('최상위 요소는 :' + s.peek()); System.out.print('스택에 있는 요소:'); 스프린트(); } } //이 코드는 Vinay Pandey에 의해 수정되었습니다.> # Python program for implementation of stack # import maxsize from sys module # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack')>
// C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack { private int[] ele; private int top; private int max; public Stack(int size) { ele = new int[size]; // Maximum size of Stack top = -1; max = size; } public void push(int item) { if (top == max - 1) { Console.WriteLine('Stack Overflow'); return; } else { ele[++top] = item; } } public int pop() { if (top == -1) { Console.WriteLine('Stack is Empty'); return -1; } else { Console.WriteLine('{0} popped from stack ', ele[top]); return ele[top--]; } } public int peek() { if (top == -1) { Console.WriteLine('Stack is Empty'); return -1; } else { Console.WriteLine('{0} popped from stack ', ele[top]); return ele[top]; } } public void printStack() { if (top == -1) { Console.WriteLine('Stack is Empty'); return; } else { for (int i = 0; i <= top; i++) { Console.WriteLine('{0} pushed into stack', ele[i]); } } } } // Driver program to test above functions class Program { static void Main() { Stack p = new Stack(5); p.push(10); p.push(20); p.push(30); p.printStack(); p.pop(); } } }> /* javascript program to implement basic stack operations */ var t = -1; var MAX = 1000; var a = Array(MAX).fill(0); // Maximum size of Stack function isEmpty() { return (t < 0); } function push(x) { if (t>= (MAX - 1)) { console.log('스택 오버플로'); 거짓을 반환; } else { t+=1; a[t] = x; console.log(x + ' 스택에 푸시됨 '); 사실을 반환; } } 함수 팝() { if (t< 0) { console.log('Stack Underflow'); return 0; } else { var x = a[t]; t-=1; return x; } } function peek() { if (t < 0) { console.log('Stack Underflow'); return 0; } else { var x = a[t]; return x; } } function print() { for (i = t; i>-1; i--) { console.log(' ' + a[i]); } } 푸시(10); 푸시(20); 푸시(30); console.log(pop() + ' 스택에서 팝됨'); console.log(' 최상위 요소는 :' + peek()); console.log(' 스택에 있는 요소: '); 인쇄(); // 이 코드는 Rajput-Ji가 제공한 것입니다.> // 스택의 연결 리스트 구현을 위한 C++ 프로그램 #포함하다 사용하여 네임스페이스 성병; //스택을 나타내는 구조체 수업 스택노드 { 공공의: 정수 데이터; 스택노드* 다음; }; 스택노드* 새로운노드(정수 데이터) { 스택노드* 스택노드 = 새로운 스택노드(); 스택노드->데이터 = 데이터; 스택노드->다음 = 없는; 반품 스택노드; } 정수 비었다(스택노드* 뿌리) { 반품 !뿌리; } 무효의 푸시(스택노드** 뿌리, 정수 데이터) { 스택노드* 스택노드 = 새로운노드(데이터); 스택노드->다음 = *뿌리; *뿌리 = 스택노드; 시합 << 데이터 << ' 푸시='' to='' 스택<='' span=''>N'; } 정수 팝(스택노드** 뿌리) { 만약에 (비었다(*뿌리)) 반품 INT_MIN; 스택노드* 온도 = *뿌리; *뿌리 = (*뿌리)->다음; 정수 터진 = 온도->데이터; 무료(온도); 반품 터진; } 정수 몰래 엿보다(스택노드* 뿌리) { 만약에 (비었다(뿌리)) 반품 INT_MIN; 반품 뿌리->데이터; } // 드라이버 코드 정수 기본() { 스택노드* 뿌리 = 없는; 푸시(&뿌리, 10); 푸시(&뿌리, 이십); 푸시(&뿌리, 30); 시합 << 팝(&뿌리) << ' 스택에서 튀어나옴N'; 시합 << '최상위 요소는 ' << 몰래 엿보다(뿌리) << 끝; 시합 <<'스택에 존재하는 요소: '; //스택의 모든 요소를 인쇄합니다. ~하는 동안(!비었다(뿌리)) { //스택의 최상위 요소를 인쇄합니다. 시합 << 몰래 엿보다(뿌리) <<' '; //스택의 최상위 요소 제거 팝(&뿌리); } 반품 0; } // 이것은 rathbhupendra가 제공한 코드입니다.씨 // C program for linked list implementation of stack #include #include #include // A structure to represent a stack struct StackNode { int data; struct StackNode* next; }; struct StackNode* newNode(int data) { struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode)); stackNode->데이터 = 데이터; stackNode->다음 = NULL; stackNode를 반환; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data); stackNode->next = *루트; *루트 = 스택노드; printf('%d가 스택에 푸시되었습니다
', data); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN; struct StackNode* temp = *root; *루트 = (*루트)->다음; int popped = 임시->데이터; 무료(임시); 리턴이 터졌습니다. } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN; 루트->데이터를 반환합니다. } int main() { struct StackNode* 루트 = NULL; push(&루트, 10); push(&루트, 20); push(&루트, 30); printf('%d가 스택에서 팝되었습니다
', pop(&root)); printf('최상위 요소는 %d입니다
', peek(root)); 0을 반환합니다. }> 자바 // Java Code for Linked List Implementation public class StackAsLinkedList { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(data + ' pushed to stack'); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } // Driver code public static void main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); sll.push(10); sll.push(20); sll.push(30); System.out.println(sll.pop() + ' popped from stack'); System.out.println('Top element is ' + sll.peek()); sll.push(10); sll.push(20); sll.push(30); System.out.println(sll.pop() + ' popped from stack'); System.out.println('Top element is ' + sll.peek()); } }> 파이썬 # Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)> 씨# // C# Code for Linked List Implementation using System; public class StackAsLinkedList { StackNode root; public class StackNode { public int data; public StackNode next; public StackNode(int data) { this.data = data; } } public bool isEmpty() { if (root == null) { return true; } else return false; } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } Console.WriteLine(data + ' pushed to stack'); } public int pop() { int popped = int.MinValue; if (root == null) { Console.WriteLine('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { Console.WriteLine('Stack is empty'); return int.MinValue; } else { return root.data; } } // Driver code public static void Main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); sll.push(10); sll.push(20); sll.push(30); Console.WriteLine(sll.pop() + ' popped from stack'); Console.WriteLine('Top element is ' + sll.peek()); } } /* This code contributed by PrinciRaj1992 */> 자바스크립트 >
산출 10 pushed to stack 20 pushed to stack 30 pushed to stack 30 popped from stack Top element is 20 Elements present in stack : 20 10>
연결리스트 구현의 장점:
- 스택의 연결 목록 구현은 런타임 시 필요에 따라 확장되거나 축소될 수 있습니다.
- JVM과 같은 많은 가상 머신에서 사용됩니다.
Linked List 구현의 단점:
- 포인터 관련으로 인해 추가 메모리가 필요합니다.
- 스택에서는 무작위 접근이 불가능합니다.
// C program for linked list implementation of stack #include #include #include // A structure to represent a stack struct StackNode { int data; struct StackNode* next; }; struct StackNode* newNode(int data) { struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode)); stackNode->데이터 = 데이터; stackNode->다음 = NULL; stackNode를 반환; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data); stackNode->next = *루트; *루트 = 스택노드; printf('%d가 스택에 푸시되었습니다
', data); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN; struct StackNode* temp = *root; *루트 = (*루트)->다음; int popped = 임시->데이터; 무료(임시); 리턴이 터졌습니다. } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN; 루트->데이터를 반환합니다. } int main() { struct StackNode* 루트 = NULL; push(&루트, 10); push(&루트, 20); push(&루트, 30); printf('%d가 스택에서 팝되었습니다
', pop(&root)); printf('최상위 요소는 %d입니다
', peek(root)); 0을 반환합니다. }> // Java Code for Linked List Implementation public class StackAsLinkedList { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(data + ' pushed to stack'); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } // Driver code public static void main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); sll.push(10); sll.push(20); sll.push(30); System.out.println(sll.pop() + ' popped from stack'); System.out.println('Top element is ' + sll.peek()); sll.push(10); sll.push(20); sll.push(30); System.out.println(sll.pop() + ' popped from stack'); System.out.println('Top element is ' + sll.peek()); } }> # Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)> // C# Code for Linked List Implementation using System; public class StackAsLinkedList { StackNode root; public class StackNode { public int data; public StackNode next; public StackNode(int data) { this.data = data; } } public bool isEmpty() { if (root == null) { return true; } else return false; } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } Console.WriteLine(data + ' pushed to stack'); } public int pop() { int popped = int.MinValue; if (root == null) { Console.WriteLine('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { Console.WriteLine('Stack is empty'); return int.MinValue; } else { return root.data; } } // Driver code public static void Main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); sll.push(10); sll.push(20); sll.push(30); Console.WriteLine(sll.pop() + ' popped from stack'); Console.WriteLine('Top element is ' + sll.peek()); } } /* This code contributed by PrinciRaj1992 */> >
스택 데이터 구조에 대한 작업의 복잡성 분석:
| 운영 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 푸시() | 오(1) | 오(1) |
| 팝() | 오(1) | 오(1) |
상단() 또는 오줌 케이() | 오(1) | 오(1) |
| 비었다() | 오(1) | 오(1) 폴더 이름 바꾸기 linux |
| 가득() | 오(1) | 오(1) |
스택의 장점 데이터 구조 :
- 간단: 스택은 간단하고 이해하기 쉬운 데이터 구조이므로 다양한 애플리케이션에 적합합니다.
- 능률: 스택에 대한 푸시 및 팝 작업은 일정한 시간에 수행될 수 있습니다. (O(1)) , 데이터에 대한 효율적인 액세스를 제공합니다.
- 후입선출(LIFO): 스택은 LIFO 원칙을 따르므로 스택에 마지막으로 추가된 요소가 가장 먼저 제거됩니다. 이 동작은 함수 호출 및 식 평가와 같은 다양한 시나리오에서 유용합니다.
- 제한된 메모리 사용량: 스택은 푸시된 요소만 저장하면 되므로 다른 데이터 구조에 비해 메모리 효율성이 높습니다.
스택의 단점 데이터 구조 :
- 제한된 액세스: 스택의 요소는 맨 위에서만 액세스할 수 있으므로 스택 중간에 있는 요소를 검색하거나 수정하기가 어렵습니다.
- 오버플로 가능성: 보유할 수 있는 것보다 더 많은 요소가 스택에 푸시되면 오버플로 오류가 발생하여 데이터가 손실됩니다.
- 무작위 액세스에 적합하지 않음: 스택 s는 요소에 대한 임의 액세스를 허용하지 않으므로 특정 순서로 요소에 액세스해야 하는 애플리케이션에 적합하지 않습니다.
- 제한된 용량: 스택에는 고정된 용량이 있으므로 저장해야 하는 요소 수가 알 수 없거나 가변성이 큰 경우 제한이 될 수 있습니다.
스택 데이터 구조의 응용:
- 중위에서 후위로 /접두사 변환
- 편집자, 포토샵 등 다양한 곳에서 실행 취소 기능을 다시 실행하세요.
- 웹 브라우저의 앞으로 및 뒤로 기능
- 메모리 관리에서 모든 최신 컴퓨터는 실행 목적을 위한 기본 관리로 스택을 사용합니다. 컴퓨터 시스템에서 실행되는 각 프로그램에는 고유한 메모리 할당이 있습니다.
- 스택은 또한 컴퓨터에서 함수 호출을 구현하는 데 도움이 됩니다. 마지막으로 호출된 함수는 항상 먼저 완료됩니다.
관련 기사:
- 단일 연결 리스트를 사용하여 스택 구현
- 구현을 통한 스택 데이터 구조의 기본 작업
- SDE 인터뷰에서 질문된 스택 데이터 구조의 상위 50가지 문제
- 스택의 응용, 장점 및 단점
- 경쟁력 있는 프로그래밍을 위한 스택