スタックのデータ構造 です 線形データ構造 それに続く LIFO (後入れ先出し) の原則 したがって、最後に挿入された要素が最初にポップアウトされます。この記事では、スタックの基本、スタック上の操作、その実装、利点、欠点をすべて取り上げ、スタックに基づくすべての問題を解決するのに役立ちます。

目次

• スタックデータ構造とは何ですか?
• スタックデータ構造の基本操作
• スタック データ構造における isEmpty 操作
• リンクリストを使用したスタックデータ構造の実装
• スタックデータ構造に対する操作の複雑さの分析
• スタックデータ構造の利点
• スタックデータ構造の欠点
• スタックデータ構造の応用

スタックデータ構造とは何ですか?

スタック です 線形データ構造 に基づく LIFO(後入れ先出し)の原則 新しい要素の挿入と既存の要素の削除は、 として表される同じ端で行われます。 上 スタックの。

スタックを実装するには、 スタックの先頭へのポインタ 、これは最後に挿入される要素です。 スタックの最上位にある要素にのみアクセスできます。

スタック データ構造の表現:

スタックは LIFO (Last In First Out) 原則に従っており、最後にプッシュされた要素が最初にポップされます。

固定サイズのスタック : 名前が示すように、固定サイズ スタックのサイズは固定されており、動的に拡大または縮小することはできません。スタックがいっぱいのときに要素を追加しようとすると、オーバーフロー エラーが発生します。スタックが空で、スタックから要素を削除しようとすると、アンダーフロー エラーが発生します。

動的サイズスタック : 動的なサイズのスタックは、動的に拡大または縮小できます。スタックがいっぱいになると、新しい要素を収容できるようにサイズが自動的に増加し、スタックが空になるとサイズが減少します。このタイプのスタックは、スタックのサイズを簡単に変更できるため、リンク リストを使用して実装されます。

スタック上の基本操作 データ構造 :

スタック内で操作を行うために、特定の操作が提供されています。

• 押す（） 要素をスタックに挿入するには
• ポップ（） スタックから要素を削除するには
• 上（） スタックの最上位の要素を返します。
• isEmpty() スタックが空の場合は true を返し、それ以外の場合は false を返します。
• 一杯（） スタックがいっぱいの場合は true を返し、それ以外の場合は false を返します。

プッシュ操作のアルゴリズム:

• 要素をスタックにプッシュする前に、スタックが 満杯 。
• スタックがいっぱいの場合 (上 == 容量-1) 、 それから スタックオーバーフロー そして要素をスタックに挿入することはできません。
• それ以外の場合は、top の値を 1 ずつ増やします。 (上 = 上 + 1) 新しい値が次の場所に挿入されます トップの位置 。
• 要素は、次の値に到達するまでスタックにプッシュできます。 容量 スタックの。

ポップ操作のアルゴリズム:

• スタックから要素をポップする前に、スタックが 空の 。
• スタックが空の場合 (top == -1)、 スタックのアンダーフロー そしてスタックから要素を削除することはできません。
• それ以外の場合は、先頭の値を保存し、先頭の値を 1 ずつ減分します。 (上 = 上 – 1) そして保存されている上位値を返します。

トップ操作のアルゴリズム:

• スタックから最上位の要素を返す前に、スタックが空かどうかを確認します。
• スタックが空の場合 (top == -1)、単純に「Stack is empty」と出力します。
• それ以外の場合は、に格納されている要素を返します。 インデックス = トップ 。

isEmpty オペレーションのアルゴリズム :

• の値を確認します 上 スタックで。
• もし (上 == -1) 、スタックは次のようになります。 空の だから戻って 真実 。
• それ以外の場合、スタックは空ではないため、戻ります 間違い 。

isFull オペレーションのアルゴリズム:

• の値を確認します 上 スタックで。
• もし (上 == 容量-1)、 スタックは 満杯 だから戻って 真実 。
• それ以外の場合、スタックはいっぱいではないため、戻ります 間違い 。

スタックの実装 データ構造 :

スタック上で実行できる基本的な操作には、プッシュ、ポップ、ピークが含まれます。スタックを実装するには 2 つの方法があります。

• 配列の使用
• リンクリストの使用

配列ベースの実装では、プッシュ操作は、最上位要素のインデックスをインクリメントし、そのインデックスに新しい要素を格納することによって実装されます。ポップ操作は、先頭のインデックスに格納されている値を返し、先頭要素のインデックスをデクリメントすることによって実装されます。

リンク リスト ベースの実装では、プッシュ操作は、新しい要素で新しいノードを作成し、現在の最上位ノードの次のポインタを新しいノードに設定することによって実装されます。ポップ操作は、現在のトップ ノードのネクスト ポインタを次のノードに設定し、現在のトップ ノードの値を返すことによって実装されます。

; 戻る 間違い ; } それ以外 { ある [ ++ 上 ] = バツ ; コート < < バツ < < ' スタックにプッシュされました ' ; 戻る 真実 ; } } 整数 スタック::ポップ () { もし ( 上 < 0 ) { コート < < 「スタックアンダーフロー」 ; 戻る 0 ; } それ以外 { 整数 バツ = ある [ 上 -- ]; 戻る バツ ; } } 整数 スタック::ピーク () { もし ( 上 < 0 ) { コート < < 「スタックは空です」 ; 戻る 0 ; } それ以外 { 整数 バツ = ある [ 上 ]; 戻る バツ ; } } ブール スタック::isEmpty () { 戻る ( 上 < 0 ); } // 上記の機能をテストするためのドライバー プログラム 整数 主要 () { クラス スタック s ; s 。 押す ( 10 ); s 。 押す ( 二十 ); s 。 押す ( 30 ); コート < < s 。 ポップ () < < ' スタックからポップされました ' ; //ポップ後にスタックの先頭要素を出力します コート < < '最上位の要素は : ' < < s 。 ピーク () < < 終わり ; // スタック内のすべての要素を出力します。 コート < < 'スタックに存在する要素: ' ; その間 ( ！ s 。 空です ()) { // スタックの最上位要素を出力します コート < < s 。 ピーク () < < 「」 ; // スタックの最上位要素を削除します s 。 ポップ (); } 戻る 0 ; } // コードは Vinay Pandey によって変更されました C

// 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;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  スタックを返します。 } // トップが最後のインデックスと等しい場合、スタックはいっぱいです 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;  スタック->配列[++スタック->トップ] = アイテム;  printf('%d がスタックにプッシュされました
', item); } // スタックから項目を削除する関数。 top を 1 つ減らします。 int Pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top--]; } // スタックの先頭を削除せずに返す関数 int Peak(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  スタック->配列[スタック->トップ]を返します。 } // 上記関数をテストするドライバー プログラム 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('スタック オーバーフロー');  false を返します。  } else { a[++top] = x;  System.out.println(x + ' スタックにプッシュされました');  true を返します。  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#

// 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

/* 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('スタック オーバーフロー');  false を返します。  } else { t+=1;  a[t] = x;    console.log(x + ' スタック ' にプッシュされました);  true を返します。  } } 関数pop() { 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(' 最上位要素は :' + Peak());  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 のような動的なサイズの配列の場合、スタックは配列の実装とともに拡大および縮小する可能性があります]。  
 
 スタックの合計サイズは事前に定義する必要があります。  
 
 

' ; } 整数 ポップ ( スタックノード ** 根 ) { もし ( 空です ( * 根 )) 戻る INT_MIN ; スタックノード * 温度 = * 根 ; * 根 = ( * 根 ) -> 次 ; 整数 ポップした = 温度 -> データ ; 無料 ( 温度 ); 戻る ポップした ; } 整数 ピーク ( スタックノード * 根 ) { もし ( 空です ( 根 )) 戻る INT_MIN ; 戻る 根 -> データ ; } // ドライバーコード 整数 主要 () { スタックノード * 根 = ヌル ; 押す ( & 根 、 10 ); 押す ( & 根 、 二十 ); 押す ( & 根 、 30 ); コート < < ポップ ( & 根 ) < < ' スタックからポップされました ' ; コート < < '最上位の要素は ' < < ピーク ( 根 ) < < 終わり ; コート < < 'スタックに存在する要素: ' ; // スタック内のすべての要素を出力します。 その間 ( ！ 空です ( 根 )) { // スタックの最上位要素を出力します コート < < ピーク ( 根 ) < < 「」 ; // スタックの最上位要素を削除します ポップ ( & 根 ); } 戻る 0 ; } // これは rathbhupendra によって提供されたコードです C

// 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->next = NULL;  スタックノードを返します。 int isEmpty(struct StackNode* root) { return !root; } void Push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *ルート = スタックノード;  printf('%d がスタックにプッシュされました
', data); } int Pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *ルート = (*ルート)->次へ;  int ポップ = temp->data;  無料(一時);  リターンポップ。 } int Peak(struct StackNode* root) { if (isEmpty(root)) は INT_MIN を返します。  ルート->データを返します。 int main() { struct StackNode* root = NULL;  プッシュ(&root, 10);  プッシュ(&root, 20);  プッシュ(&root, 30);  printf('%d がスタックからポップされました
', Pop(&root));  printf('最上位要素は %d
', Peak(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#

// 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 */ 

JavaScript

 > 

出力 リンク リスト実装の利点:

• スタックのリンク リスト実装は、実行時のニーズに応じて拡大または縮小できます。
• JVM などの多くの仮想マシンで使用されます。

リンク リスト実装の欠点:

• ポインタが関与するため、追加のメモリが必要です。
• スタックではランダムアクセスはできません。

スタックデータ構造に対する操作の複雑さの分析:

スタックの利点 データ構造 :

• シンプルさ: スタックはシンプルで理解しやすいデータ構造であるため、幅広いアプリケーションに適しています。
• 効率： スタック上のプッシュおよびポップ操作を一定時間で実行可能 (お(1)) 、データへの効率的なアクセスを提供します。
• 後入れ先出し (LIFO): スタックは LIFO 原則に従い、スタックに追加された最後の要素が最初に削除されるようにします。この動作は、関数呼び出しや式の評価など、多​​くのシナリオで役立ちます。
• 限られたメモリ使用量: スタックは、プッシュされた要素を保存するだけでよいため、他のデータ構造と比較してメモリ効率が高くなります。

スタックの欠点 データ構造 :

• アクセス制限: スタック内の要素には最上位からのみアクセスできるため、スタックの中央にある要素を取得または変更することが困難になります。
• オーバーフローの可能性: 保持できる以上の要素がスタックにプッシュされると、オーバーフロー エラーが発生し、データが失われます。
• ランダムアクセスには適していません: スタック 要素へのランダム アクセスが許可されていないため、要素に特定の順序でアクセスする必要があるアプリケーションには適していません。
• 限られた容量: スタックの容量は固定されているため、保存する必要がある要素の数が不明な場合や変動が大きい場合には、制限となる可能性があります。

スタック データ構造のアプリケーション:

• インフィックスからポストフィックスへ /プレフィックス変換
• エディターやフォトショップなど、多くの場所でやり直し/元に戻す機能。
• Web ブラウザの進む機能と戻る機能
• メモリ管理では、最新のコンピュータは実行目的の主な管理としてスタックを使用します。コンピュータ システムで実行されている各プログラムには、独自のメモリ割り当てがあります。
• スタックは、コンピューターでの関数呼び出しの実装にも役立ちます。最後に呼び出された関数が常に最初に完了します。

関連記事：

• 単一リンクリストを使用してスタックを実装する
• スタック データ構造の基本操作と実装
• SDE のインタビューで質問されるスタック データ構造に関する問題トップ 50
• スタックの用途、メリット、デメリット
  
• 競技プログラミング用スタック