스택 데이터 구조란 무엇입니까? 완전한 튜토리얼
스택 데이터 구조 는 선형 데이터 구조 다음은 LIFO(후입선출) 원리 이므로 마지막으로 삽입된 요소가 가장 먼저 팝아웃됩니다. 이 기사에서는 스택 기반의 모든 문제를 해결하는 데 도움이 되는 스택의 모든 기본 사항, 스택 작업, 구현, 장점, 단점을 다룰 것입니다.
내용의 테이블
- 스택 데이터 구조란 무엇입니까?
- 스택 데이터 구조의 기본 작업
- 스택 데이터 구조에 대한 연산의 복잡성 분석
- 스택 데이터 구조의 장점
- 스택 데이터 구조의 단점
- 스택 데이터 구조의 응용
스택 데이터 구조란 무엇입니까?
스택 는 선형 데이터 구조 기반으로 LIFO(후입선출) 원리 새 요소의 삽입과 기존 요소의 제거는 다음과 같이 표시된 동일한 끝에서 발생합니다. 맨 위 스택의.
스택을 구현하려면 다음을 유지해야 합니다. 스택의 맨 위를 가리키는 포인터 , 이는 삽입될 마지막 요소입니다. 스택의 맨 위에 있는 요소에만 액세스할 수 있습니다.
스택 데이터 구조의 표현:
스택은 LIFO(Last In First Out) 원리를 따르므로 마지막에 푸시된 요소가 먼저 팝됩니다.
고정 크기 스택 : 이름에서 알 수 있듯이 고정 크기 스택은 고정된 크기를 가지며 동적으로 늘어나거나 줄어들 수 없습니다. 스택이 가득 차고 여기에 요소를 추가하려고 하면 오버플로 오류가 발생합니다. 스택이 비어 있고 스택에서 요소를 제거하려고 하면 언더플로 오류가 발생합니다.
스택의 기본 작업 데이터 구조 :
스택을 조작하기 위해 우리에게 제공되는 특정 작업이 있습니다.
- 푸시() 스택에 요소를 삽입하려면
- 팝() 스택에서 요소를 제거하려면
- 맨 위() 스택의 최상위 요소를 반환합니다.
- 비었다() 스택이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
- 가득() 스택이 가득 차면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
푸시 작업 알고리즘:
- 요소를 스택에 푸시하기 전에 스택이 있는지 확인합니다. 가득한 .
- 스택이 가득 찬 경우 (상단 == 용량-1) , 그 다음에 스택 오버플로 스택에 요소를 삽입할 수 없습니다.
- 그렇지 않으면 top 값을 1씩 증가시킵니다. (상단 = 상단 + 1) 새 값은 다음 위치에 삽입됩니다. 최상위 위치 .
- 요소는 우리가 도달할 때까지 스택에 푸시될 수 있습니다. 용량 스택의.
팝 작업을 위한 알고리즘:
- 스택에서 요소를 팝하기 전에 스택이 다음과 같은지 확인합니다. 비어 있는 .
- 스택이 비어 있으면(top == -1) 스택 언더플로우 그리고 스택에서 어떤 요소도 제거할 수 없습니다.
- 그렇지 않으면 상단에 값을 저장하고 상단의 값을 1씩 감소시킵니다. (상단 = 상단 – 1) 저장된 최고 값을 반환합니다.
최고 작업을 위한 알고리즘:
- 스택에서 최상위 요소를 반환하기 전에 스택이 비어 있는지 확인합니다.
- 스택이 비어 있으면(top == -1) 간단히 Stack isempty를 인쇄합니다.
- 그렇지 않으면 다음에 저장된 요소를 반환합니다. 지수=상단 .
isEmpty 작업의 알고리즘 :
- 값을 확인하세요. 맨 위 스택에.
- 만약에 (상단 == -1) , 그러면 스택은 비어 있는 그러니 돌아오세요 진실 .
- 그렇지 않으면 스택이 비어 있지 않으므로 반환합니다. 거짓 .
isFull 작업의 알고리즘:
- 값을 확인하세요. 맨 위 스택에.
- 만약에 (상단 == 용량-1), 그러면 스택은 가득한 그러니 돌아오세요 진실 .
- 그렇지 않으면 스택이 가득 차지 않으므로 반환합니다. 거짓 .
스택 구현 데이터 구조 :
스택에서 수행할 수 있는 기본 작업에는 푸시(push), 팝(pop), 픽(peek)이 있습니다. 스택을 구현하는 방법에는 두 가지가 있습니다.
- 배열 사용
- 연결리스트 사용
배열 기반 구현에서 푸시 작업은 최상위 요소의 인덱스를 증가시키고 해당 인덱스에 새 요소를 저장하여 구현됩니다. 팝 연산은 최상위 인덱스에 저장된 값을 반환한 다음 최상위 요소의 인덱스를 감소시키는 방식으로 구현됩니다.
연결된 목록 기반 구현에서 푸시 작업은 새 요소로 새 노드를 만들고 현재 최상위 노드의 다음 포인터를 새 노드로 설정하여 구현됩니다. Pop 연산은 현재 최상위 노드의 다음 포인터를 다음 노드로 설정하고 현재 최상위 노드의 값을 반환하는 방식으로 구현됩니다.
; 반품 거짓 ; } 또 다른 { ㅏ [ ++ 맨 위 ] = 엑스 ; 시합 < < 엑스 < < ' 스택에 푸시됨 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 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++의 벡터, Python의 목록, Java의 ArrayList와 같은 동적 크기 배열의 경우 배열 구현에 따라 스택이 늘어나고 줄어들 수도 있습니다].
- 스택의 전체 크기를 미리 정의해야 합니다.
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
// 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 */ 연결리스트 구현의 장점:
- 스택의 연결 목록 구현은 런타임 시 필요에 따라 확장되거나 축소될 수 있습니다.
- JVM과 같은 많은 가상 머신에서 사용됩니다.
Linked List 구현의 단점:
- 포인터 관련으로 인해 추가 메모리가 필요합니다.
- 스택에서는 무작위 접근이 불가능합니다.
스택 데이터 구조에 대한 작업의 복잡성 분석:
| 운영 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 푸시() | 오(1) | 오(1) |
| 팝() | 오(1) | 오(1) |
| 상단() 또는 오줌 케이() | 오(1) | 오(1) |
| 비었다() | 오(1) | 오(1) |
| 가득() | 오(1) | 오(1) |
스택의 장점 데이터 구조 :
- 간단: 스택은 간단하고 이해하기 쉬운 데이터 구조이므로 다양한 애플리케이션에 적합합니다.
- 능률: 스택에 대한 푸시 및 팝 작업은 일정한 시간에 수행될 수 있습니다. (O(1)) , 데이터에 대한 효율적인 액세스를 제공합니다.
- 후입선출(LIFO): 스택은 LIFO 원칙을 따르므로 스택에 마지막으로 추가된 요소가 가장 먼저 제거됩니다. 이 동작은 함수 호출 및 식 평가와 같은 다양한 시나리오에서 유용합니다.
- 제한된 메모리 사용량: 스택은 푸시된 요소만 저장하면 되므로 다른 데이터 구조에 비해 메모리 효율성이 높습니다.
스택의 단점 데이터 구조 :
- 제한된 액세스: 스택의 요소는 맨 위에서만 액세스할 수 있으므로 스택 중간에 있는 요소를 검색하거나 수정하기가 어렵습니다.
- 오버플로 가능성: 보유할 수 있는 것보다 더 많은 요소가 스택에 푸시되면 오버플로 오류가 발생하여 데이터가 손실됩니다.
- 무작위 액세스에 적합하지 않음: 스택 s는 요소에 대한 임의 액세스를 허용하지 않으므로 특정 순서로 요소에 액세스해야 하는 애플리케이션에 적합하지 않습니다.
- 제한된 용량: 스택에는 고정된 용량이 있으므로 저장해야 하는 요소 수가 알 수 없거나 가변성이 큰 경우 제한이 될 수 있습니다.
스택 데이터 구조의 응용:
- 중위에서 후위로 /접두사 변환
- 편집자, 포토샵 등 다양한 곳에서 실행 취소 기능을 다시 실행하세요.
- 웹 브라우저의 앞으로 및 뒤로 기능
- 메모리 관리에서 모든 최신 컴퓨터는 실행 목적을 위한 기본 관리로 스택을 사용합니다. 컴퓨터 시스템에서 실행되는 각 프로그램에는 고유한 메모리 할당이 있습니다.
- 스택은 또한 컴퓨터에서 함수 호출을 구현하는 데 도움이 됩니다. 마지막으로 호출된 함수는 항상 먼저 완료됩니다.
관련 기사:
- 단일 연결 리스트를 사용하여 스택 구현
- 구현을 통한 스택 데이터 구조의 기본 작업
- SDE 인터뷰에서 질문된 스택 데이터 구조의 상위 50가지 문제
- 스택의 응용, 장점 및 단점
- 경쟁력 있는 프로그래밍을 위한 스택
