创建数据结构 两层 这代表了两层。实施 两层 应该只使用一个数组，即两个堆栈应该使用相同的数组来存储元素。以下功能必须由 两层 . push1（int x）–>将x推到第一个堆栈 push2（int x）–>将x推到第二个堆栈 pop1（）–>从第一个堆栈中弹出一个元素，并返回弹出的元素 pop2（）–>从第二个堆栈中弹出一个元素，并返回弹出的元素 实施 两层 应该节省空间。
null
方法1（将空间分成两半） 实现两个堆栈的一种简单方法是将数组分成两半，并将半空间分配给两个堆栈，即对stack1使用arr[0]到arr[n/2]，对stack2使用arr[（n/2）+1]到arr[n-1]，其中arr[]是用于实现两个堆栈的数组，数组大小为n。 这种方法的问题是对数组空间的低效利用。即使arr[]中有可用空间，堆栈推送操作也可能导致堆栈溢出。例如，假设数组大小为6，我们将3个元素推送到stack1，而不将任何内容推送到第二个stack2。当我们把第4个元素推到stack1时，即使我们在数组中还有3个元素的空间，也会出现溢出。
C++
#include <iostream> #include <stdlib.h> using namespace std; class twoStacks { int * arr; int size; int top1, top2; public : // Constructor twoStacks( int n) { size = n; arr = new int [n]; top1 = n / 2 + 1; top2 = n / 2; } // Method to push an element x to stack1 void push1( int x) { // There is at least one empty // space for new element if (top1 > 0) { top1--; arr[top1] = x; } else { cout << "Stack Overflow" << " By element :" << x << endl; return ; } } // Method to push an element // x to stack2 void push2( int x) { // There is at least one empty // space for new element if (top2 < size - 1) { top2++; arr[top2] = x; } else { cout << "Stack Overflow" << " By element :" << x << endl; return ; } } // Method to pop an element from first stack int pop1() { if (top1 <= size / 2) { int x = arr[top1]; top1++; return x; } else { cout << "Stack UnderFlow" ; exit (1); } } // Method to pop an element // from second stack int pop2() { if (top2 >= size / 2 + 1) { int x = arr[top2]; top2--; return x; } else { cout << "Stack UnderFlow" ; exit (1); } } }; /* Driver program to test twoStacks class */ int main() { twoStacks ts(5); ts.push1(5); ts.push2(10); ts.push2(15); ts.push1(11); ts.push2(7); cout << "Popped element from stack1 is " << " : " << ts.pop1() << endl; ts.push2(40); cout << "Popped element from stack2 is " << ": " << ts.pop2() << endl; return 0; } |
JAVA
import java.util.*; class twoStacks { int [] arr; int size; int top1, top2; // Constructor twoStacks( int n) { size = n; arr = new int [n]; top1 = n / 2 + 1 ; top2 = n / 2 ; } // Method to push an element x to stack1 void push1( int x) { // There is at least one empty // space for new element if (top1 > 0 ) { top1--; arr[top1] = x; } else { System.out.print( "Stack Overflow" + " By element :" + x + "" ); return ; } } // Method to push an element // x to stack2 void push2( int x) { // There is at least one empty // space for new element if (top2 < size - 1 ) { top2++; arr[top2] = x; } else { System.out.print( "Stack Overflow" + " By element :" + x + "" ); return ; } } // Method to pop an element from first stack int pop1() { if (top1 <= size / 2 ) { int x = arr[top1]; top1++; return x; } else { System.out.print( "Stack UnderFlow" ); System.exit( 1 ); } return 0 ; } // Method to pop an element // from second stack int pop2() { if (top2 >= size / 2 + 1 ) { int x = arr[top2]; top2--; return x; } else { System.out.print( "Stack UnderFlow" ); System.exit( 1 ); } return 1 ; } }; class GFG { /* Driver program to test twStacks class */ public static void main(String[] args) { twoStacks ts = new twoStacks( 5 ); ts.push1( 5 ); ts.push2( 10 ); ts.push2( 15 ); ts.push1( 11 ); ts.push2( 7 ); System.out.print( "Popped element from stack1 is " + " : " + ts.pop1() + "" ); ts.push2( 40 ); System.out.print( "Popped element from stack2 is " + ": " + ts.pop2() + "" ); } } // This code is contributed by aashish1995 |
C#
using System; using System.Collections.Generic; public class twoStacks { public int [] arr; public int size; public int top1, top2; // Constructor public twoStacks( int n) { size = n; arr = new int [n]; top1 = n / 2 + 1; top2 = n / 2; } // Method to push an element x to stack1 public void push1( int x) { // There is at least one empty // space for new element if (top1 > 0) { top1--; arr[top1] = x; } else { Console.Write( "Stack Overflow" + " By element :" + x + "" ); return ; } } // Method to push an element // x to stack2 public void push2( int x) { // There is at least one empty // space for new element if (top2 < size - 1) { top2++; arr[top2] = x; } else { Console.Write( "Stack Overflow" + " By element :" + x + "" ); return ; } } // Method to pop an element from first stack public int pop1() { if (top1 <= size / 2) { int x = arr[top1]; top1++; return x; } else { Console.Write( "Stack UnderFlow" ); } return 0; } // Method to pop an element // from second stack public int pop2() { if (top2 >= size / 2 + 1) { int x = arr[top2]; top2--; return x; } else { Console.Write( "Stack UnderFlow" ); } return 1; } }; public class GFG { /* Driver program to test twStacks class */ public static void Main(String[] args) { twoStacks ts = new twoStacks(5); ts.push1(5); ts.push2(10); ts.push2(15); ts.push1(11); ts.push2(7); Console.Write( "Popped element from stack1 is " + " : " + ts.pop1() + "" ); ts.push2(40); Console.Write( "Popped element from stack2 is " + ": " + ts.pop2() + "" ); } } // This code is contributed by umadevi9616 |
Javascript
<script> class twoStacks { // Constructor constructor(n) { this .arr = new Array(n); this .size = n; this .top1 = Math.floor(n / 2) + 1; this .top2 = Math.floor(n / 2); } // Method to push an element x to stack1 push1(x) { // There is at least one empty // space for new element if ( this .top1 > 0) { this .top1--; this .arr[ this .top1] = x; } else { document.write( "Stack Overflow" + " By element :" + x + "<br>" ); return ; } } // Method to push an element // x to stack2 push2(x) { // There is at least one empty // space for new element if ( this .top2 < this .size - 1) { this .top2++; this .arr[ this .top2] = x; } else { document.write( "Stack Overflow" + " By element :" + x + "<br>" ); return ; } } // Method to pop an element from first stack pop1() { if ( this .top1 <= this .size / 2) { let x = this .arr[ this .top1]; this .top1++; return x; } else { document.write( "Stack UnderFlow" ); } return 0; } // Method to pop an element // from second stack pop2() { if ( this .top2 >= Math.floor( this .size / 2) + 1) { let x = this .arr[ this .top2]; this .top2--; return x; } else { document.write( "Stack UnderFlow" ); } return 1; } } /* Driver program to test twStacks class */ let ts = new twoStacks(5); ts.push1(5); ts.push2(10); ts.push2(15); ts.push1(11); ts.push2(7); document.write( "Popped element from stack1 is " + " : " + ts.pop1() + "<br>" ); ts.push2(40); document.write( "Popped element from stack2 is " + ": " + ts.pop2() + "<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Stack Overflow By element :7Popped element from stack1 is : 11Stack Overflow By element :40Popped element from stack2 is : 15
复杂性分析：
- 时间复杂性：
- 推送操作： O（1）
- Pop操作： O（1）
- 辅助空间： O（N）。 使用数组实现堆栈so。这不是如上所述的空间优化方法。
方法2（节省空间的实现） 这种方法有效地利用了可用空间。如果arr[]中有可用空间，则不会导致溢出。这个想法是从arr[]的两个极端角落开始两个堆栈。stack1从最左边的元素开始，stack1中的第一个元素被推到索引0处。stack2从最右边的角落开始，stack2中的第一个元素被推到索引（n-1）处。两个堆栈的增长（或收缩）方向相反。为了检查溢出，我们只需要检查两个堆栈顶部元素之间的空间。此检查在下面的代码中突出显示。
C++
#include <iostream> #include <stdlib.h> using namespace std; class twoStacks { int * arr; int size; int top1, top2; public : twoStacks( int n) // constructor { size = n; arr = new int [n]; top1 = -1; top2 = size; } // Method to push an element x to stack1 void push1( int x) { // There is at least one empty space for new element if (top1 < top2 - 1) { top1++; arr[top1] = x; } else { cout << "Stack Overflow" ; exit (1); } } // Method to push an element x to stack2 void push2( int x) { // There is at least one empty // space for new element if (top1 < top2 - 1) { top2--; arr[top2] = x; } else { cout << "Stack Overflow" ; exit (1); } } // Method to pop an element from first stack int pop1() { if (top1 >= 0) { int x = arr[top1]; top1--; return x; } else { cout << "Stack UnderFlow" ; exit (1); } } // Method to pop an element from second stack int pop2() { if (top2 < size) { int x = arr[top2]; top2++; return x; } else { cout << "Stack UnderFlow" ; exit (1); } } }; /* Driver program to test twoStacks class */ int main() { twoStacks ts(5); ts.push1(5); ts.push2(10); ts.push2(15); ts.push1(11); ts.push2(7); cout << "Popped element from stack1 is " << ts.pop1(); ts.push2(40); cout << "Popped element from stack2 is " << ts.pop2(); return 0; } |
JAVA
// Java program to implement two stacks in a // single array class TwoStacks { int size; int top1, top2; int arr[]; // Constructor TwoStacks( int n) { arr = new int [n]; size = n; top1 = - 1 ; top2 = size; } // Method to push an element x to stack1 void push1( int x) { // There is at least one empty space for // new element if (top1 < top2 - 1 ) { top1++; arr[top1] = x; } else { System.out.println( "Stack Overflow" ); System.exit( 1 ); } } // Method to push an element x to stack2 void push2( int x) { // There is at least one empty space for // new element if (top1 < top2 - 1 ) { top2--; arr[top2] = x; } else { System.out.println( "Stack Overflow" ); System.exit( 1 ); } } // Method to pop an element from first stack int pop1() { if (top1 >= 0 ) { int x = arr[top1]; top1--; return x; } else { System.out.println( "Stack Underflow" ); System.exit( 1 ); } return 0 ; } // Method to pop an element from second stack int pop2() { if (top2 < size) { int x = arr[top2]; top2++; return x; } else { System.out.println( "Stack Underflow" ); System.exit( 1 ); } return 0 ; } // Driver program to test twoStack class public static void main(String args[]) { TwoStacks ts = new TwoStacks( 5 ); ts.push1( 5 ); ts.push2( 10 ); ts.push2( 15 ); ts.push1( 11 ); ts.push2( 7 ); System.out.println( "Popped element from" + " stack1 is " + ts.pop1()); ts.push2( 40 ); System.out.println( "Popped element from" + " stack2 is " + ts.pop2()); } } // This code has been contributed by // Amit Khandelwal(Amit Khandelwal 1). |
python
# Python Script to Implement two stacks in a list class twoStacks: def __init__( self , n): # constructor self .size = n self .arr = [ None ] * n self .top1 = - 1 self .top2 = self .size # Method to push an element x to stack1 def push1( self , x): # There is at least one empty space for new element if self .top1 < self .top2 - 1 : self .top1 = self .top1 + 1 self .arr[ self .top1] = x else : print ( "Stack Overflow " ) exit( 1 ) # Method to push an element x to stack2 def push2( self , x): # There is at least one empty space for new element if self .top1 < self .top2 - 1 : self .top2 = self .top2 - 1 self .arr[ self .top2] = x else : print ( "Stack Overflow " ) exit( 1 ) # Method to pop an element from first stack def pop1( self ): if self .top1 > = 0 : x = self .arr[ self .top1] self .top1 = self .top1 - 1 return x else : print ( "Stack Underflow " ) exit( 1 ) # Method to pop an element from second stack def pop2( self ): if self .top2 < self .size: x = self .arr[ self .top2] self .top2 = self .top2 + 1 return x else : print ( "Stack Underflow " ) exit() # Driver program to test twoStacks class ts = twoStacks( 5 ) ts.push1( 5 ) ts.push2( 10 ) ts.push2( 15 ) ts.push1( 11 ) ts.push2( 7 ) print ( "Popped element from stack1 is " + str (ts.pop1())) ts.push2( 40 ) print ( "Popped element from stack2 is " + str (ts.pop2())) # This code is contributed by Sunny Karira |
C#
// C# program to implement two // stacks in a single array using System; public class TwoStacks { public int size; public int top1, top2; public int [] arr; // Constructor public TwoStacks( int n) { arr = new int [n]; size = n; top1 = -1; top2 = size; } // Method to push an element x to stack1 public virtual void push1( int x) { // There is at least one empty // space for new element if (top1 < top2 - 1) { top1++; arr[top1] = x; } else { Console.WriteLine( "Stack Overflow" ); Environment.Exit(1); } } // Method to push an element x to stack2 public virtual void push2( int x) { // There is at least one empty // space for new element if (top1 < top2 - 1) { top2--; arr[top2] = x; } else { Console.WriteLine( "Stack Overflow" ); Environment.Exit(1); } } // Method to pop an element // from first stack public virtual int pop1() { if (top1 >= 0) { int x = arr[top1]; top1--; return x; } else { Console.WriteLine( "Stack Underflow" ); Environment.Exit(1); } return 0; } // Method to pop an element // from second stack public virtual int pop2() { if (top2 < size) { int x = arr[top2]; top2++; return x; } else { Console.WriteLine( "Stack Underflow" ); Environment.Exit(1); } return 0; } // Driver Code public static void Main( string [] args) { TwoStacks ts = new TwoStacks(5); ts.push1(5); ts.push2(10); ts.push2(15); ts.push1(11); ts.push2(7); Console.WriteLine( "Popped element from" + " stack1 is " + ts.pop1()); ts.push2(40); Console.WriteLine( "Popped element from" + " stack2 is " + ts.pop2()); } } // This code is contributed by Shrikant13 |
PHP
<?php // PHP program to implement two // stacks in a single array class twoStacks { private $arr ; private $size ; private $top1 ; private $top2 ; function __construct( $n ) { $this ->size = $n ; $this ->arr = array (); $this ->top1 = -1; $this ->top2 = $this ->size; } // Method to push an element x to stack1 function push1( $x ) { // There is at least one empty // space for new element if ( $this ->top1 < $this ->top2 - 1) { $this ->top1++; $this ->arr[ $this ->top1] = $x ; } else { echo "Stack Overflow" ; exit (); } } // Method to push an element x to stack2 function push2( $x ) { // There is at least one empty space // for new element if ( $this ->top1 < $this ->top2 - 1) { $this ->top2--; $this ->arr[ $this ->top2] = $x ; } else { echo "Stack Overflow" ; exit (); } } // Method to pop an element // from first stack function pop1() { if ( $this ->top1 >= 0 ) { $x = $this ->arr[ $this ->top1]; $this ->top1--; return $x ; } else { echo "Stack UnderFlow" ; exit (); } } // Method to pop an element from // second stack function pop2() { if ( $this ->top2 < $this ->size) { $x = $this ->arr[ $this ->top2]; $this ->top2++; return $x ; } else { echo "Stack UnderFlow" ; exit (); } } }; // Driver Code $ts = new twoStacks(5); $ts ->push1(5); $ts ->push2(10); $ts ->push2(15); $ts ->push1(11); $ts ->push2(7); echo "Popped element from stack1 is " . $ts ->pop1(); $ts ->push2(40); echo "Popped element from stack2 is " . $ts ->pop2(); // This code is contributed by // rathbhupendra ?> |
输出：
Popped element from stack1 is 11Popped element from stack2 is 40
复杂性分析：
- 时间复杂性：
- 推送操作： O（1）
- Pop操作： O（1）
- 辅助空间： O（N）。 使用数组实现堆栈，因此这是一种空间优化方法。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
